package com.lhcai.lc.category.doublepointer;

/**
 * 11. 盛最多水的容器
 * type: 双指针
 *
 * @author liuhuaicai
 * @create 2024-10-13 10:44
 */
public class Lc11 {
    public static void main(String[] args) {
        Lc11 lc11 = new Lc11();
        System.out.println(lc11.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
    }
    /**
     * 模拟这个问题，是O（n^2），会超时
     * <p>
     * 设置两个指针。一个指针在数组的左边，一个指针在数组的右边。始终移动指向较低线条的指针。可以保证有一边永远是大边
     * 计算容器水量： 两边之距 * 短边高度
     *
     * @param height 数组
     * @return 容器水量
     */

    public int maxArea(int[] height) {
        // 双指针
        int res = Integer.MIN_VALUE;
        int left = 0;
        int right = height.length - 1;
        while (right > left) {
            int hei = Math.min(height[left], height[right]);
            int wei = right - left;
            int container = hei * wei;
            if (container >= res) {
                res = container;
            }
            if (height[left] >= height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return res;
    }


    // 超出时间限制  56 / 63 个通过的测试用例
//    public int maxAreaFor(int[] height) {
//        // 双重循环法
//        int res = Integer.MIN_VALUE;
//        for (int i = 0; i < height.length; i++) {
//            for (int j = i + 1; j < height.length; j++) {
//                int hei = Math.min(height[i], height[j]);
//                int wei = j - i;
//                int container = hei * wei;
//                res = Math.max(res, container);
//            }
//        }
//        return res;
//    }
}
